package lc.q300_350;

/**
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 *
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
 * 实现 NumMatrix 类：
 *
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
 */
public class Q304 {

    public static void main(String[] args) {
        NumMatrix numMatrix = new NumMatrix(new int[][]{
                new int[]{3, 0, 1, 4, 2},
                new int[]{5, 6, 3, 2, 1},
                new int[]{1, 2, 0, 1, 5},
                new int[]{4, 1, 0, 1, 7},
                new int[]{1, 0, 3, 0, 5},
                new int[]{5, 6, 3, 2, 1}
        });
        System.out.println(numMatrix.sumRegion(2,1,4,3));
        System.out.println(numMatrix.sumRegion(1,1,2,2));
        System.out.println(numMatrix.sumRegion(1,2,2,4));
        System.out.println(numMatrix.sumRegion(0,2,2,4));
    }

    public static class NumMatrix {

        private int[][] matrix = null;
        private int[][] sumMatrix = null;

        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            // 前缀和矩阵sum[i][j]代表0,0,i,j包含的区域的和
            sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
            // 现将i==0和j==0的赋值上去
            sumMatrix[1][1] = matrix[0][0];
            for (int i = 1; i < matrix[0].length; i++) {
                sumMatrix[1][i + 1] = matrix[0][i] + sumMatrix[1][i];
            }
            for (int i = 1; i < matrix.length; i++) {
                sumMatrix[i+1][1] = matrix[i][0] + sumMatrix[i][1];
            }
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    // i，j的值
                    sumMatrix[i+1][j+ 1] = matrix[i][j] + sumMatrix[i][j+1] + sumMatrix[i+1][j] - sumMatrix[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            // 增加一个边
            int r2c2 = sumMatrix[row2+1][col2+1];
            return r2c2 - sumMatrix[row1][col2+1] - sumMatrix[row2+1][col1] + sumMatrix[row1][col1];
        }
    }
}
